/**
 * @file 322.CoinChange.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-26
 * 
 * @copyright Copyright (c) 2021
 * 
 * 完全背包
 * 518.零钱兑换II -- 组合 **
 * 377.组合总和IV -- 排列 -- 内外循环的顺序
 *                      -- 外循环是物品，求的是组合；反之是排列
 * 322.零钱兑换
 * 279.完全平方数
 * 139.单词拆分
 */

#include <cmath>

#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 518.
    int changeII(int amount, const vector<int> &coins)
    {
        // dp[j] 凑成j金额的硬币组合数
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
    // 377.
    int combinationSum4(const vector<int> &nums, int target)
    {
        // nums不重复，求排列数
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int j = 1; j <= target; ++j) {
            // nums放到内循环，保证每次都从头开始取
            // 以保证排列顺序
            for (int i = 0; i < nums.size(); ++i) {
                if (j >= nums[i]) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        // print(dp);
        return dp[target];
    }
    // 322. 求凑成amout的最少硬币数
    int coinChange(const vector<int> &coins, int amount)
    {
        // 这才是正宗完全背包
        vector<int> dp(amount + 1, INT32_MAX - 1);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); ++i) {
            for (int j = coins[i]; j <= amount; ++j) {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        // return dp[amount];
        return dp[amount] == INT32_MAX - 1 ? -1 : dp[amount];
    }
    // 279.
    int numSquares(int n)
    {
        // 先生成平方数组
        int size = sqrt(n);
        vector<int> square(size, 0);
        for (int i = 0; i < size; ++i) {
            square[i] = (i + 1) * (i + 1);
        }
        cout << "square=";
        print(square);
        // 然后就是完全背包，每个数不限次数取
        // dp[j] 和为j的完全平方数的最少数量
        vector<int> dp(n + 1, 1000);
        dp[0] = 0;
        for (int i = 0; i < size; ++i) {
            for (int j = square[i]; j <= n; ++j) {
                dp[j] = min(dp[j], dp[j - square[i]] + 1);
            }
        }
        return dp[n];
    }
    // 135.
    bool wordBreak(string s, const vector<string> &wordDict)
    {
        // dp[i] 表示s[:i]能否break
        // 取决于：
        // 1 其前缀子串s[:j]是否为True -> dp[j] (j遍历指针,0<=j<=i)
        // 2 剩余子串s[j:i]是否在单词表中

        int n = s.length();
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                string subPre = s.substr(j, i - j); // 剩余子串
                if (dp[j] && st.find(subPre) != st.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

void test518()
{
    cout << Solution().changeII(5, {1, 2, 5}) << endl;
    cout << Solution().changeII(3, {2}) << endl;
    cout << Solution().changeII(10, {10}) << endl;
}

void test377()
{
    cout << Solution().combinationSum4({1, 2, 3}, 4) << endl;
    cout << Solution().combinationSum4({10, 20, 30, 40, 50,
                                        60, 70, 80, 90, 100,
                                        110, 120, 130, 140, 150,
                                        160, 170, 180, 190, 200,
                                        210, 220, 230, 240, 250,
                                        260, 270, 280, 290, 300,
                                        310, 320, 330, 340, 350,
                                        360, 370, 380, 390, 400,
                                        410, 420, 430, 440, 450,
                                        460, 470, 480, 490, 500,
                                        510, 520, 530, 540, 550,
                                        560, 570, 580, 590, 600,
                                        610, 620, 630, 640, 650,
                                        660, 670, 680, 690, 700,
                                        710, 720, 730, 740, 750,
                                        760, 770, 780, 790, 800,
                                        810, 820, 830, 840, 850,
                                        860, 870, 880, 890, 900,
                                        910, 920, 930, 940, 950,
                                        960, 970, 980, 990, 111},
                                       999)
         << endl;
}

void test322()
{
    cout << Solution().coinChange({1, 2, 5}, 11) << endl;
    cout << Solution().coinChange({2}, 3) << endl;
    cout << Solution().coinChange({1}, 0) << endl;
    cout << Solution().coinChange({1}, 1) << endl;
    cout << Solution().coinChange({1}, 2) << endl;
}

void test279()
{
    cout << Solution().numSquares(12) << endl;
    cout << Solution().numSquares(13) << endl;
}

void test139()
{
    cout << Solution().wordBreak("leetcode", {"leet", "code"}) << endl;
    cout << Solution().wordBreak("applepenapple", {"apple", "pen"}) << endl;
    cout << Solution().wordBreak("catsandog", {"cats", "dog", "sand", "and", "cat"}) << endl;
}

int main()
{
    // test518();
    // test377();
    // test322();
    // test279();
    test139();
    return 0;
}